#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: longest_palindrome.py 
@version:
@time: 2023/12/24

对于一个回文子串来说，其子结构就是其中间部分仍为回文子串。

我们可以用一个二维数组来表示本字符串的两位之间是否是回文子串，
在初始化时默认只有二维数组的对角线上是True，其余位置默认为False。

i/i  a  b  c  b  a
a    1  0  0  0  0
b    0  1  0  0  0
c    0  0  1  0  0
b    0  0  0  1  0
a    0  0  0  0  1

"""


def longest_palindrome(s):
    # 最长 左右 位置
    right = left = 0
    dp = []
    for i in range(len(s)):
        dp.append([0] * len(s))
        dp[i][i] = 1
    """
a  b  c  b  a
         ^  ^
         i  j


a  b  c  b  a
      ^  ^
      i  j    
    """
    i = len(s) - 2
    while i >= 0:
        j = i + 1
        while j < len(s):
            # 当判断出s[i]=s[j]时，就继续判断dp[i-1][j+1]是否是回文串
            # 如果是，那么s[i]到s[j]的子串就是回文串，再更新dp[i][j]为1.
            flag = s[i] == s[j] and (dp[i + 1][j - 1] or j - i == 1)
            if flag:
                dp[i][j] = 1
            # 需要一边寻找回文子串一边判断是否为最长的回文子串，当确认s[i]和s[j]是一个回文子串之后，
            # 需要对其长度与目前为止最长回文子串长度进行对比，如果更长，则对目前最长回文子串的长度和首位位置进行更新。
            if dp[i][j] and right - left < j - i:
                right = j
                left = i
            # 向两边扩展
            j += 1
            i -= 1
    return s[left:right + 1]


res = longest_palindrome('badad')
print(res)
